The present invention relates generally to computer implemented and automatic processing of auctions.
Users of the World Wide Web are familiar with the various services available on the Web for locating content of interest. Search engines are provided by a number of entities and search capabilities are embedded in many web sites. Web users are also familiar with the manner in which search results are presented by the various search engines and utilities.
“Organic” search results (i.e., search results which appear because they have some objective measure of relevance to the keywords of the search query) are typically presented on the left hand side (i.e., the West) of a search results page. In addition, “sponsored” search results (i.e., search results which appear because the sponsors have paid for placement in response to specific search keywords) are also presented in search results pages at a variety of locations including at the top (i.e., the North), the right hand side (i.e., the East), and the bottom (i.e., the South) of the search results page. A wide variety of sophisticated algorithms have been developed for identifying, ranking, and placing sponsored search results with the intent of enhancing the likelihood that users viewing search results pages will select them. As this sort of advertising is part of the economic foundation of the Web and the Internet, continued advancement in the performance of such algorithms is desirable.
In the framework of sponsored search, advertisers typically compete in an auction to place their ads on a web page. In the widely used pay-per-click model, each advertiser is typically charged only when her ad receives a click. The position in which an ad is displayed has an impact on its likelihood of being clicked, and advertisers' preferences follow accordingly. However, it is generally assumed that all clicks (independent of the ads' position) have the same value for an advertiser. Consequently, search engines typically establish a price for a click that is not conditioned on the position where the ad is presented.
The most widely used mechanism for sponsored search auctions combines the sort-by-revenue allocation and Generalized Second Price (GSP) rules. Specifically, bidders are ranked according to the revenue the auctioneer expects to obtain from them and higher ranked ads are allocated to higher slots, while the price charged to each bidder is the minimum amount necessary for her to maintain her position in the ranking. Unfortunately, such a mechanism cannot easily handle additional constraints.